package com.example.demo.basics.arit;

/**
 * @author aqua
 * @description 二分查找
 * 特点    有序 1/2查找
 * 缺点
 * 其缺点是要求待查表为有序表，且插入删除困难。
 * 因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
 *
 * 思路:
 * 定义方法  参数 数组集合   关键字 最短  最长
 * 1.先判断不满足条件  最短大于最长  最小集合大于关键字 最大集合小于关键字
 * 先判断不满足条件 return
 * 2.找中间点 (low +high) /2
 * if 大于中间点 higt-1 在递归遍历  否 low+1  无 return
 *
 *循环解决
 * @date 2020年11月03 2:31
 * @email 1301584033@qq.com
 */
public class BinarySearch {
    
    /** 
    * @Description:
    * @Param: [arr, key, low, high]    数组集合   关键字 最短  最长
    * @return:  
    * @Author: aqua
    * @Date: 2020/11/3 
    */ 
    public static int recursionBinarySearch(int[] arr,int key,int low,int high) {
        //先判断不满足条件  最短大于最长  最小集合大于关键字 最大集合小于关键字
        if (low > high || arr[low] > key || arr[high] < key) {
            return -1;
        }
        int middle = (low + high) / 2;
        if (arr[middle] > key) {
            recursionBinarySearch(arr, key, low, middle - 1);
        } else if (arr[low] < key) {
            recursionBinarySearch(arr, key, low, middle + 1);
        } else {
            return middle;
        }
        return -1;
    }

    /**
     * 不使用递归的二分查找
     *title:commonBinarySearch
     *@param arr
     *@param key
     *@return 关键字位置
     */
    public static int commonBinarySearch(int[] arr,int key){
        int low=0;
        int high=arr.length-1;
        int middle;
        //先判断不满足条件  最短大于最长  最小集合大于关键字 最大集合小于关键字
        if (low > high || arr[low] > key || arr[high] < key) {
            return -1;
        }
        while (low <= high){
             middle=(low+high)/2;
            if(arr[middle]<key){
                low=middle+1;
            }else if(arr[middle]>key){
                high=middle-1;
            }else {
                return middle;
            }
        }
        return  -1;

    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int key = 4;
        //int position = recursionBinarySearch(arr,key,0,arr.length - 1);

        int position = commonBinarySearch(arr, key);

        if (position == -1) {
            System.out.println("查找的是" + key + ",序列中没有该数！");
        } else {
            System.out.println("查找的是" + key + ",找到位置为：" + position);

        }
    }

}
